package oct2013.linkednode;

import java.util.HashMap;

public class CopyListwithRandomPointer {
	public RandomListNode copyRandomList(RandomListNode head) {
		RandomListNode cur = head;
		while (cur != null) {
			RandomListNode newNode = new RandomListNode(cur.label);
			newNode.next = cur.next;
			cur.next = newNode;
			cur = newNode.next;
		}
		cur = head;
		while (cur != null) {
			if (cur.random != null)
				cur.next.random = cur.random.next;
			cur = cur.next.next;
		}
		cur = head;
		RandomListNode newHead = null;
		if (cur != null) {
			newHead = cur.next;
		}
		while (cur != null) {
			RandomListNode newCur = cur.next;
			cur.next = newCur.next;
			cur = cur.next;
			if (cur != null)
				newCur.next = cur.next;
		}
		return newHead;
	}

	public RandomListNode copyRandomListByHash(RandomListNode head) {
		HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
		RandomListNode cur = head;
		while (cur != null) {
			RandomListNode newNode = new RandomListNode(cur.label);
			map.put(cur, newNode);
			cur = cur.next;
		}
		cur = head;
		while (cur != null) {
			RandomListNode newNode = map.get(cur);
			newNode.next = map.get(cur.next);
			newNode.random = map.get(cur.random);
			cur = cur.next;
		}
		return map.get(head);
	}
}
